package dataStructures;

public class OrderedDoubleList <K extends Comparable<K>, V> implements OrderedDictionary<K,V> {
	
	  /**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	// Node at the head of the list.
    protected DListNode<EntryClass<K, V>> head;

    // Node at the tail of the list.
    protected DListNode<EntryClass<K, V>> tail;

    // Number of elements in the list.
    protected int currentSize;


    public OrderedDoubleList( )
    {
        head = null;
        tail = null;
        currentSize = 0;
    }

	@Override
	public boolean isEmpty() {
		return currentSize==0;
	}

	@Override
	public int size() {
		return currentSize;
	}

	@Override
	public V find(K key) {
		DListNode<EntryClass<K, V>> node = findNearest(key);
        if ( node == null )
            return null;
        else if(node.getElement().getKey().equals(key))
        	return node.getElement().getValue();
        else
            return null;
	}

	@Override
	public V insert(K key, V value) {
		DListNode<EntryClass<K, V>> aux = new DListNode<EntryClass<K, V>>(new EntryClass<K, V>(key, value));
		if(this.isEmpty()){
			currentSize++;
			head = aux;
			return value;
		}
		else{
			DListNode<EntryClass<K, V>> node;
			node = findNearest(key);
			if(node != null && node.getElement().getKey().equals(key)){
				V auxV = node.getElement().getValue();
				node.setElement(new EntryClass<K, V>(key, value));
				return auxV;
			}
			else{ 
				currentSize++;
				if(node == null){
					aux.setPrevious(tail);
					tail.setNext(aux);
					tail = aux;
					
				}
				else if(node.getPrevious() == null){
					head = aux;
					aux.setNext(node);
					node.setPrevious(aux);
				}
				else{
					aux.setNext(node);
					aux.setPrevious(node.getPrevious());
					node.setPrevious(aux);
					node = node.getPrevious();
					node.setNext(aux);
				}
			return value;
			}
		}		
	}

	@Override
	public V remove(K key) {
		DListNode<EntryClass<K, V>> node;
		node = findNearest(key);
		if(node == null || node.getElement().getKey().compareTo(key) != 0){
			return null;
		}
		else{
			currentSize--;
			V auxV = node.getElement().getValue();
			if(node.getPrevious() == null){
				node = node.getNext();
				head = node;
				if(node != null)
					node.setPrevious(null);
			}
			else if(node.getNext() == null){
				node = node.getPrevious();
				tail = node;
				node.setNext(null);
			}
			else{
				DListNode<EntryClass<K, V>> aux = node.getPrevious();
				aux = aux.getNext();
				node.setNext(aux);
				aux.setPrevious(node);
			}
			return auxV;
		}
		
	}

	@Override
	public Iterator<Entry<K, V>> iterator() {
		// TODO Auto-generated method stub
		return new OrderedDoubleLIterator<K,V>(head, tail);
	}

	@Override
	public EntryClass<K, V> minEntry() throws EmptyDictionaryException {
		return head.getElement();
	}

	@Override
	public EntryClass<K, V> maxEntry() throws EmptyDictionaryException {
		return tail.getElement();

	}
	
	private DListNode<EntryClass<K, V>> findNearest(K key){
		DListNode<EntryClass<K, V>> node = head;
		while(node != null && node.getElement().getKey().compareTo(key)<0){
			node = node.getNext();
		}
		return node;
		
	}
	
}
